package com.company;

/**
 * @author zhf
 * @date 2022/1/21
 */
//给你一个二叉树的根节点 root ，返回其 最大路径和 。
public class MaxPathSum {
    public static void main(String[] args) {
        Integer[] array = {5,4,8,11,null,13,4,7,2,null,null,null,1};
        TreeNode root = TreeUtil.CreateTree(array);
        MaxPathSum maxPathSum = new MaxPathSum();
        int ans = maxPathSum.maxPathSum(root);
        System.out.println(ans);
    }
    int ans = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return ans;
    }

    //可以使用递归求解


    public int dfs(TreeNode root){
        if (root == null) {
            return 0;
        }
        int leftMax = Math.max(0,dfs(root.left));
        int rightMax = Math.max(0,dfs(root.right));
        //计算当前最大路径和；
        ans = Math.max(ans,leftMax + rightMax + root.val);

        //计算当前路径和
        return Math.max(leftMax,rightMax) + root.val;
    }
}
